package lcr;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test0084 {
    public static void main(String[] args) {
        new Solution0084_1().permuteUnique(new int[]{0,1,0,0,9});
    }
}

class Solution0084_1 {
    List<List<Integer>> ans= new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        backtrack(nums,0,new ArrayList<>(nums.length));
        return ans;
    }
    public void backtrack(int[] nums,int records,List<Integer> list) {
        int length = nums.length;
        int size = list.size();
        if (size==length){
            ans.add(new ArrayList<>(list));
            return;
        }

        int pre=Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            int flag = 1 << i;

            if ((records&flag)>0||(i!=0&&pre==num)) continue;

            pre=num;
            records|=flag;
            list.add(num);

            backtrack(nums,records,list);

            list.remove(size);
            records^=flag;
        }

    }


}
